﻿//#define _CRT_SECURE_NO_WARNINGS 1
//
//#include<iostream>
//#include<string>
//using namespace std;

//
//int is_(int n, int k)
//{
//    int count = 0;
//
//    while (n > 0)
//    {
//        if (n % 2 == 1)
//        {
//            count++;
//        }
//        n /= 2;
//    }
//    if (count == k)
//    {
//        return 1;
//    }
//    else {
//        return 0;
//    }
//}
//int main()
//{
//    int nums[]={}
//    int sum = 0;
//    for (int i = 0; i < nums.size(); i++)
//    {
//        if (is_(nums[i], k))
//        {
//            sum += nums[i];
//        }
//    }
//    return sum;
//}

//int main() {
//	int a = 10;
//	int b = 5;
//	// int& ra;   // 该条语句编译时会出错
//	int& ra = a;//多次引用
//	ra = b;
//	printf("%p %p %d\n", &a, &ra,ra);
//}

//void f(int)
//{
//	cout << "f(int)" << endl;
//}
//void f(int*)
//{
//	cout << "f(int*)" << endl;
//}
//int main()
//{
//	f(0);
//	f(NULL);
//	f((int*)NULL);
//	return 0;
//}
//int main()
//{
//    int x = 10;
//    auto a = &x;
//    auto* b = &x;
//    auto& c = x;
//    cout << typeid(a).name() << endl;
//    cout << typeid(b).name() << endl;
//    cout << typeid(c).name() << endl;
//    *a = 20;
//    *b = 30;
//    c = 40;
//    return 0;
//}



//int GetMonthDay(int year, int month, int day)
//{
//    int days[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
//
//    if (month == 2 && ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)))
//    {
//        days[2] += 1;
//    }
//    int sum = 0;
//    for (int i = 0; i < month; i++)
//    {
//        sum += days[i];
//    }
//    sum += day;
//    return sum;
//}
//
//int main() {
//    int a, b, c;
//    cin >> a >> b >> c;
//    cout << GetMonthDay(a, b, c);
//
//
//}
//
//void GetMonthDay(int year, int day)
//{
//    int days[12] = { 31, 59, 90, 120, 151, 180, 212, 243, 273, 304, 334, 365 };
//
//    if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0))
//    {
//        for (int i = 1; i < 12; i++)
//        {
//            days[i]++;
//        }
//    }
//    int i = 0;
//    for (i; i < 12; i++)
//    {
//        if ((day - days[i]) <= 0)
//        {
//            if (i != 0)
//            {
//                day -= days[i-1];
//            }
//            break;
//        }
//        
//    }
//    
//    printf("%d-%02d-%02d\n", year, i + 1, day);
//
//}
//
//
//int main() {
//    int a=2436;
//    int b = 187;
//     // 注意 while 处理多个 case
//       GetMonthDay(a, b);
//    
//}
//
//#include <iostream>
//#include <cstdio>
//using namespace std;
//int dayTab[2][13] = {
//    {0,31,28,31,30,31,30,31,31,30,31,30,31},
//    {0,31,29,31,30,31,30,31,31,30,31,30,31}
//};
//
//bool IsLeapYear(int year) {            //是否为闰年
//    return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
//}
//
//int main() {
//    int year=2436, month, day;
//    int number = 187;
//     {
//        month = 0;
//        int row = IsLeapYear(year);
//        while (number > dayTab[row][month]) {          //用number来递减确定确定月份
//            number -= dayTab[row][month];
//            month++;
//        }
//        day = number;                //不足月剩下的number确定日
//        printf("%04d-%02d-%02d\n", year, month, day);
//    }
//    return 0;
//}
//
//
//#include <iostream>
//using namespace std;
//
//
//
//void GetMonthDay(int year, int day)
//{
//    //                31 28 31 30 31 30 31  31  30 31 30 31
//    int days[12] = { 31, 59, 91, 120, 151, 181, 212, 244, 274, 305, 335, 365 };
//
//    if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0))
//    {
//        for (int i = 1; i < 12; i++)
//        {
//            days[i]++;
//        }
//    }
//    int i = 0;
//    for (i; i < 12; i++)
//    {
//        if ((day - days[i]) <= 0)
//        {
//            if (i != 0)
//            {
//                day -= days[i - 1];
//            }
//            break;
//        }
//    }
//    printf("%d-%02d-%02d\n", year, i + 1, day);
//
//}
//
//
//int main() {
//    int a, b;
//    while (cin >> a >> b) { // 注意 while 处理多个 case
//        GetMonthDay(a, b);
//    }
//}
//// 64 位输出请用 printf("%lld")
//
//#include <iostream>
//using namespace std;



//void GetMonthDay(int year, int day)
//{
//
//    int days[2][12] = {
//    { 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365 },
//    { 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335, 366 }
//    };
//    int tag = 0;
//    if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0))
//    {
//        tag = 1;
//    }
//    int i = 0;
//    for (i; i < 12; i++)
//    {
//        if ((day - days[tag][i]) <= 0)
//        {
//            if (i != 0)
//            {
//                day -= days[tag][i - 1];
//            }
//            break;
//        }
//    }
//    printf("%d-%02d-%02d\n", year, i + 1, day);
//
//}
//
//
//int main() {
//    int a, b;
//    while (cin >> a >> b) { // 注意 while 处理多个 case
//        GetMonthDay(a, b);
//    }
//}
//// 64 位输出请用 printf("%lld")

//class A
//{
//public:
//    A(int a)
//        :_a1(a)
//        , _a2(_a1)
//    {}
//    void Print()
//
//    {
//
//        cout << _a1 << " " << _a2 << endl;
//
//    }
//
//private:
//
//    int _a2;
//
//    int _a1;
//
//};
//
//
//
//int main()
//
//{
//
//    A aa(1);
//
//    aa.Print();
//
//}

//class A
//{
//public:
//    A(int a)
//        :_a1(a)
//        , _a2(_a1)
//    {}
//
//    void Print() {
//        cout << _a1 << " " << _a2 << endl;
//    }
//private:
//    int _a2;
//    int _a1;
//};
//int main() {
//    A aa(1);
//    aa.Print();
//}
//#include <iostream>
//using namespace std;
//class A
//{
//public:
//	A()
//	{
//		_count++;
//	}
//	A(const A& a)
//	{
//		_count++;
//	}
//	~A()
//	{
//		_count--;
//	}
//	static int GetCount()
//	{
//		return _count;
//	}
//private:
//	static int _count;
//};
//int A::_count = 0;
//
//int main()
//{
//	A a1;
//	A a2;
//	A(a3);
//	cout << A::GetCount() << endl;
//
//	return 0;
//}
//int main()
//{
//	Stack<int> s1;
//}
//
//#include <iostream>                                               
//using namespace std;
//int IsLeapYear(int year)
//{
//    if (((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)))
//    {
//        return 1;
//    }
//    return 0;
//}
//
//int GetMonthDay(int year, int month)
//{
//    //             1  2  3   4  5   6  7  8  9  10  11  12
//    int a[13] = { 0, 31,28,31,30,31,30,31,31,30,31,30,31 };
//    if (month == 2 && ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)))
//    {
//        a[2] + 1;
//    }
//    int sum = 0;
//    for (int i=0; i < month; i++)
//    {
//        sum += a[i];
//    }
//    for (int i = 0; i < year; i++)
//    {
//        if (IsLeapYear(i)) {
//            sum += 366;
//        }
//        else sum += 365;
//    }
//    return sum;
//}
//                    
//int main() {
//    int year1, month1, day1, year2, month2, day2;
//    scanf("%4d%2d%2d", &year1, &month1, &day1);
//    scanf("%4d%2d%2d", &year2, &month2, &day2);
//    int Day1 = GetMonthDay(year1, month1);
//    int Day2 = GetMonthDay(year2, month2);
//    Day1 += day1;
//    Day2 += day2;
//    if (Day1 > Day2)
//        cout << Day1 - Day2+1;
//    else
//        cout << Day2 - Day1+1;
//
//}
//class A
//{
//public:
//
//private:
//
//};
//
//
//int main()
//{
//	class A* pclassa = new class A[5];
//
//	delete pclassa;
//}

//int main()
//{
//	string s = "ww";
//	s+="a";
//	string a = "d";
//	a=s.substr(1);
//	cout << a;
//	string s1 = to_string(123);
//}

//int main()
//{
//    string str;
//    getline(cin, str);
//    vector<int> table(26);
//
//    for (int i = 0; i < str.size(); i++)
//    {
//        table[str[i] - 'A']++;
//    }
//    int max = 0;
//    for (int i = 0; i < 26; i++)
//    {
//        if (table[i] > max)
//        {
//            max = table[i];
//        }
//    }
//    for (int i = 0; i < 26; i++)
//    {
//        if (table[i] == max)
//        {
//            char a = 'A' + i;
//            cout << a;
//        }
//
//    }
//
//    /*for (auto e : str)
//    {
//        cout << e;
//    }*/
//    return 0;
//}
//
//void find(vector<int>& a, int& mini, int& seci)
//{
//	for (int i = 0; i < a.size(); i++)
//	{
//		if (a[i] < a[mini] && a[i] != 0)
//		{
//			mini = i;
//		}
//	}
//	for (int i = 0; i < a.size(); i++)
//	{
//		if (a[i] < a[seci] && a[i] != 0 && i != mini)
//		{
//			seci = i;
//		}
//	}
//}
//int main()
//{
//	int n = 0;
//	cin >> n;
//	vector<int> a(n);
//	for (int i = 0; i < n; i++)
//	{
//		cin >> a[i];
//	}
//	int sum = 0;
//	int min = 0, sec = 0;
//	while (--n)
//	{
//		find(a, min, sec);
//		sum += a[min];
//		sum += a[sec];
//		a[min] = a[sec] = 0;
//		a[min] = sum;
//		min = 0, sec = 0;
//	}
//	cout << sum;
//
//
//	/*for (auto e : a)
//	{
//		cout << e;
//	}*/
//	return 0;
//}

//int main()
//{
//	int w = 0;
//	cin >> w;
//	int n = 0;
//	cin >> n;
//	w += n;
//	while (w>7)
//	{
//		w -= 7;
//	}
//	cout << w;
//
//}
//class Solution {
//public:
//    int minCostClimbingStairs(vector<int>& cost) {
//        int n = cost.size();
//        vector<int>dp(n + 1);
//        dp[0] = dp[1] = 0;
//
//        for (int i = 2; i <= n; i++)
//        {
//            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
//        }
//        return dp[n];
//
//    }
//};

//class Solution {
//public:
//    int uniquePaths(int m, int n) {
//        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
//        dp[0][1] = 1;
//
//        for (int i = 1; i <= m; i++)
//        {
//            for (int j = 1; j <= n; j++)
//            {
//                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
//            }
//        }
//        return dp[m][n];
//
//
//
//    }
//};

//class Solution {
//public:
//    int uniquePathsWithObstacles(vector<vector<int>>& ob) {
//        int m = ob.size(), n = ob[0].size();
//        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
//        dp[0][1] = 1;
//        for (int i = 1; i <= m; i++)
//        {
//            for (int j = 1; j <= n; j++)
//            {
//                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
//                if (ob[i - 1][j - 1] == 1)
//                {
//                    dp[i][j] = 0;
//                }
//            }
//        }
//        return dp[m][n];
//
//
//
//
//
//
//    }
//};


//int main()
//{
//    long long i = 0;
//    long long sum = 1;
//    long long w = 1;
//    for (int i = 1; i < 42; i++)
//    {
//        w *= i;
//        //w %=1000000000;
//        //sum += w;
//        cout << w<<endl;
//    }
//    
//    return 0;
//}